#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>

/*
二叉树的遍历：

知识点：
1.先序遍历构造一棵二叉树
2.先序遍历，中序遍历，后序遍历的递归实现，非递归实现
3.层次遍历

二叉树的递归序
*/




using namespace std;

typedef struct BiTNode//二叉树节点定义
{
	char data;//节点数据
	struct BiTNode* lchild;//左孩子节点
	struct BiTNode* rchild;//右孩子节点
}BiTNode, * BiTree;//BiTNode* ==BiTree


//递归序，每个节点都有三次机会，遍历到
void f(BiTNode* root)
{
	if (root == NULL)
		return;
	f(root->lchild);
	f(root->rchild);
}





//先序遍历创建二叉树，先序字符串通过键盘输入
BiTree CreatPre()
{
	char ch = getchar();//从键盘获取一个字符
	if (ch == '#')//表示空节点
		return NULL;
	else
	{
		BiTNode* bn = (BiTNode*)malloc(sizeof(BiTNode));//创建新节点
		bn->data = ch;
		bn->lchild = CreatPre();//递归创建左子树
		bn->rchild = CreatPre();//递归创建右子树
		return bn;
	}
}

//先序遍历：根左右
void PreOrder(BiTree bt)
{
	if (bt == NULL)
		return;
	else
	{
		cout << bt->data;
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}



//中序遍历：左根右
void InOrder(BiTree bt)
{
	if (bt == NULL)
		return;
	else
	{
		InOrder(bt->lchild);
		cout << bt->data;
		InOrder(bt->rchild);
	}
}

////后序遍历：左右根
void PostOrder(BiTree bt)
{
	if (bt == NULL)
		return;
	else
	{
		PostOrder(bt->lchild);
		PostOrder(bt->rchild);
		cout << bt->data;
	}
}


//层次遍历（利用STL的队列）
void LevelOrder(BiTree bt)
{
	if (bt == NULL)
		return;
	queue<BiTNode*>q;//创建一个队列
	q.push(bt);//
	BiTNode* p;
	while (!q.empty())//队列不空，则继续处理
	{
		p = q.front();//获取队头元素
		cout << p->data;//再打印
		if (p->lchild != NULL)
			q.push(p->lchild);
		if (p->rchild != NULL)
			q.push(p->rchild);
		q.pop();//删除队头元素
	}
	cout << endl;
}





//先序遍历的非递归版本：利用栈来模拟
//根节点入栈，如果栈不空，就弹出一个，弹出就打印，然后让右孩子入栈，再让左孩子入栈
void pre(BiTNode* root)
{
	if (root == NULL)
		return;
	//弹出就打印
	stack<BiTNode*>s;//创建一个栈
	s.push(root);//根节点入栈
	while (!s.empty())//如果栈不为空
	{
		root = s.top();
		cout << root->data << " ";
		s.pop();//弹出就打印
		//如果有右孩子，先压右孩子，然后再压左孩子，因为进出栈刚好是逆序的
		if (root->rchild != NULL)
			s.push(root->rchild);//右孩子入栈
		if (root->lchild != NULL)
			s.push(root->lchild);//左孩子入栈
	}
}


//中序遍历的非递归写法
void in(BiTNode* root)
{
	if (root == NULL)
		return;
	stack<BiTNode*>s;
	while (root != NULL || !s.empty())
	{
		//将当前节点的所有左子节点依次入栈
		if (root != NULL)
		{
			s.push(root);
			root = root->lchild;
		}
		else {
			//访问栈顶节点
			root = s.top();//先保存，然后弹出，并打印
			s.pop();
			cout << root->data;
			//将右子树当作当前节点，继续遍历其左子树
			root = root->rchild;
		}
	}
}


//后序遍历 要准备两个栈，一个栈用来
void post(BiTNode* root)
{
	if (root == NULL)
		return;
	stack<BiTNode*>s1, s2;
	s1.push(root);
	while (!s1.empty())
	{
		BiTNode* node = s1.top();
		s1.pop();
		s2.push(node);//将节点压入s2,后续处理
		//将左子树的节点和右子树的节点依次压入s1
		if (node->lchild)s1.push(node->lchild);
		if (node->rchild)s1.push(node->rchild);
	}
	//s2中保存了后续遍历的逆序结果，依次输出即可得到后续遍历的结果
	while (!s2.empty())
	{
		BiTNode* node = s2.top();
		s2.pop();
		cout << node->data;
	}
}








int main()
{

	cout << "先序构造二叉树";
	BiTree bt = CreatPre();//树1:	  ;  树2:ABCH###DE#G##F###
	/*
			A
		B       C
	#      #   #     #
	*/


	cout << "先序遍历二叉树";
	PreOrder(bt);
	cout << endl;

	cout << "中序遍历二叉树";
	InOrder(bt);
	cout << endl;

	cout << "后序遍历二叉树";
	PostOrder(bt);
	cout << endl;

	cout << "先序遍历的非递归版本";
	pre(bt);
	cout << endl;

	cout << "中序遍历的非递归版本";
	in(bt);
	cout << endl;

	cout << "后序遍历的非递归版本";
	post(bt);
	cout << endl;


	cout << endl;

	return 0;
}






